package com.cqs.leetcode.tree;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author lixiaowen
 * @create 2019-12-22
 */
public class TrieTree {


    private class Node {
        private char val;
        private Node[] children = new Node[128];
        private boolean isLeaf;

        public Node(char val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
        }

        public Node() {
        }
    }

    private Node root = new Node();


    public TrieTree() {

    }

    public void insert(String word) {
        if (word == null || word.length() == 0) return;
        char[] chars = word.toCharArray();
        Node parent = root;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (parent.children[c] == null) {
                parent.children[c] = new Node(c, false);
            }
            //设置为叶子结点
            if (i == chars.length- 1){
                parent.children[chars[chars.length - 1]].isLeaf = true;
            }
            parent = parent.children[c];
        }


    }

    /**
     * 简单的BFS
     *
     * @param word
     * @return
     */
    public boolean search(String word) {
        if (word.length() == 0) return false;
        Node node = root;
        int i = -1;
        while (++i < word.length()) {
            Node child = node.children[word.charAt(i)];
            if (child == null || child.val != word.charAt(i)) return false;
            if (i == word.length() - 1) return child.isLeaf;
            node = child;
        }
        return false;

    }

    public boolean startsWith(String prefix) {
        if (prefix.length() == 0) return false;
        Node node = root;
        int i = -1;
        while (++i < prefix.length()) {
            Node child = node.children[prefix.charAt(i)];
            if (child == null || child.val != prefix.charAt(i)) return false;
            node = child;
        }
        return true;
    }

    public static void main(String[] args) {
        TrieTree obj = new TrieTree();
        Map<String,String> testCase = new LinkedHashMap<>();
        testCase.put("world","world");
        testCase.forEach((world,prefix) ->{
            obj.insert(world);
            boolean wr = obj.search(world);
            boolean pr = obj.startsWith(prefix);
            System.out.println(wr + "\t" + pr);
        });

    }
}
